BOJ_2461_대표 선수

투 포인터(Two-Pointers)를 활용해서 푸는 문제

각 학급의 대표를 선출하되, 대표의 최소 능력과 최대 능력 차이가 가장 작아야 한다

정렬한 후 맨 앞에서부터 포인터를 옮겨가며 최대/최소를 갱신했다
포인터를 어떤 규칙으로 옮길까 고민하다 최솟값 포인터를 올리기로 했다

오름차순 정렬된 상태이고, 서로 같은 능력치가 없다면
작은 것의 인덱스를 +1 하며 찾을 때 정확하게 값을 갱신할 수 있기 때문이다

능력치가 10^9 이하랬는데, 잘못봐서 10^8 + 1로 초기화를 해서 첫 제출에 틀렸다
그 다음 제출은 맞았다 ㅎㅎ

import sys  
  
input = sys.stdin.readline  
  
N, M = map(int, input().split())  
  
power = [sorted(list(map(int, input().split()))) for i in range(N)]  
  
# 각 학급별로 능력치 창이가 최소가 되도록 만들기  
# 먼저 정렬을 하고 포인터로 맨 앞에서부터 최대 최소 비교  
# 최솟값인 것만 인덱스 하나 올려주기  
  
pointer = [0] * N  
res = float('inf')  
  
while True:  
    max_power = -1  
    min_power = float('inf')  
    min_power_idx = -1  
  
    for i in range(N):  
        now_power = power[i][pointer[i]]  
  
        if now_power > max_power:  
            max_power = now_power  
  
        if now_power < min_power:  
            min_power = now_power  
            min_power_idx = i  
  
    res = min(res, max_power - min_power)  
  
    # 제일 작은 거 1개 올리기  
    pointer[min_power_idx] += 1  
    if pointer[min_power_idx] >= M:  
        break  
  
print(res)